The present invention relates to a cryptographic technique as an information security technique, and in particular, to ID-based encryption and signature technique that can use any character string as a public key.
ID-based encryption, digital signature and Signcryption systems can use any character string as a public key. Signcryption performs encryption and signing (authentication) at the same time. These are realized using a property (called pairing) of a bilinear mapping (See, for example, Identity based encryption from the Weil pairing, by D. Boneh and M. Franklin, SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003, Extended abstract in proceedings of Crypto '2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp. 213-229, 2001, Full paper: PDF. (http://crypto.stanford.edu/˜dabo/pubs.html) (hereinafter, referred to as Non-patent Document 1), F. Hess, Efficient Identity based Signature Schemes based on Pairings, In K. Nyberg and H. Heys, editors, Proceedings of SAC 2002, LNCS 2595, pp. 310-324, St. Johns, Newfoundl and, 2003. (http://www.math.tu-berlin.de/˜hess/) (hereinafter, referred to as Non-patent Document 2) and Liqun Chen and John Malone-Lee, Improved Identity-Based Signcryption (http://eprint.iacr.org/2004/114/) (hereinafter, referred to as Non-patent Document 3).
Assuming two groups G1 and G2 of order q, pairing means a mapping bilinear e from G1×G1 to G2 that satisfies the following properties:
1. For any P, QεG1, e satisfies e(aP, bQ)=e(P, Q)ab.
2. For any P, QεG1×G1, e satisfies e(P, Q)≠the identity in G2.
For any P, QεG1, there is known an efficient algorithm for calculating e(P, Q). As specific pairing, Weil pairing and Tate pairing defined on an elliptic curve on a finite field are known.
In the following, will be described encryption, digital signature and Signcryption using an ID-based system, i.e., an ID-based public key encryption system, an ID-based digital signature system, and the ID-based Signcryption.
First, will be described an ID-based public key encryption system disclosed in Non-patent Document 1.
A system that realizes the ID-based public key encryption system comprises a private key generation center instead of a certification authority that authenticates a public key. The private key generation center determines public parameters that are used in common in the system. And, for any ID (for example, an E-mail address) that each user selects as a public key, the private key generation center generates a private key for that public key, using a master key that the private key generation center keeps under strict surveillance so that the master key should not be leaked out, and delivers the generated private key to the user concerned. The private key generation center administers the ID (public key) selected by a user and the generated private key, associating the ID with the private key. A method of selecting a public key has been determined as rules in the system.
The ID-based public key encryption system comprises the following four processes. The processes (1) and (2) are performed in the private key generation center, the process (3) on the sender's side, and the process (4) on the receiver's side.
(1) Setup: Public parameters including groups and pairing used commonly in the system are generated. Further, a master key is generated. The public parameters are opened to the public. To ensure security of the entire system, the master key is kept under strict surveillance so that the master key should not be leaked to the outside including users of the system.(2) Extract: For each user, a private key of that user is generated applying the master key to a character string that can be associated with the user (such as an E-mail address of the user). On the other hand, the character string becomes a public key of the user.(3) Encrypt: Using the public parameters and a public key of a sending destination, encryption object data are encrypted.(4) Decrypt: Using the public parameters and a private key of the recipient, the encrypted data are decrypted.
Next, will be described input, output and processing in each of the above processes (1)-(4).
In the following, Z+ means a set of the positive integers, Zq a set of positive integers less than q, and Zq* a set of positive integers less than q, which is relatively prime with Zq. Further, {0, 1}* means all the binary sequences. An expression XOR means exclusive disjunction (exclusive-OR). Further, ∥ means join. In the drawings, exclusive-OR is indicated by a circle cross symbol.
(1) Setup:
Input: security parameter kεZ+
Output: the public parameters params and the master key s
Procedure:
1. Generation of a k bit prime number q
2. Selection of a group G1 of order q
3. Selection of a group G2 of order q
4. Selection of a pairing e: G1×G1→G2 
5. Selection of a generator P of G1 
6. Random selection of an element s of Zq* (sεZq*), to define Ppub=sP
7. Selection of a hash function H1: {0, 1}*→G1*
8. Selection of a hash function H2: G2→{0, 1}n for some integer n
9. Output of the public parameters params=<q, G1, G2, e, n, P, Ppub, H1, H2>
10. Output of the master key s
(2) Extract:
Input: the public parameters params, the master key s, and any character string ID used as a public key
Output: a private key dID corresponding to ID
Procedure:
1. Calculation of the hash function QID=H1(ID) of ID, for the given ID (IDε{0, 1}*) included in the set of all the binary sequences
2. Calculation of the private key dID corresponding to ID, using the master key s and the hash value of ID (calculation of dID=sQID)
3. Output of the private key dID 
(3) Encrypt:
Input: encryption object data M, the public parameters params and the public key ID
Output: encrypted data C=(C1, C2)
Procedure:
1. Calculation of QID=H1(ID)εG1*
2. Random selection of rεZq*
3. Calculation of C1=rP
4. Calculation of gID=e(QID, Ppub)
5. Calculation of h=H2(gIDr)
6. Calculation of C2=M XOR h
7. Output of encrypted data (C1, C2)
(4) Decrypt:
Input: the encrypted data (C1, C2), the public parameters params and the private key dID 
Output: decrypted data M
Procedure:
1. Calculation of g=e(dID, C1)
2. Calculation of h=H2(g)
3. Calculation of M=C2 XOR h
4. Output of decrypted data M
Next, will be described an ID-based digital signature system disclosed in Non-patent Document 2.
Fundamentally, the system for realizing an ID-based digital signature is similar to the above-described ID-based public key encryption system. For any character string ID (for example, an E-mail address) that each user selects as a public key, a private key generation center generates a secret key corresponding to that public key and delivers the generated private key to the user concerned. A user on the sender side uses his private key to make his signature. Receiving a massage added with the signature, a user on the receiver side verifies the signature using the public key.
The ID-based digital signature system comprises the following four processes. The processes (1) and (2) are performed in the key generation center, the process (3) on the sender's side, and the process (4) on the receiver's side.
(1) Setup: Public parameters including groups and pairing used commonly in the system are generated. Further, a master key is generated. The public parameters are opened to the public. To ensure security of the entire system, the master key is kept under strict surveillance so that the master key should not be leaked to the outside including users of the system.(2) Extract: For each user, a private key of that user is generated applying the master key to a character string that can be associated with the user (such as an E-mail address of the user). On the other hand, the character string becomes a public key of that user.(3) Sign: Using the public parameters and a private key of a signer, his signature is generated.(4) Verify: Signature verification is performed using the public parameters and a public key of the sender.
Next, will be described input, output and processing specifications in each of the above processes (1)-(4).
(1) Setup:
Input: security parameter kεZ+
Output: the public parameters params and the master key s
Procedure:
1. Generation of a k bit prime number q
2. Selection of a group G1 of order q
3. Selection of a group G2 of order q
4. Selection of a pairing e: G1×G1→G2 
5. Selection of a generator P of G1 
6. Random selection of sεZq, to define Ppub=sP
7. Selection of a hash function H1: {0, 1}*→G1*
8. Selection of a hash function H2: {0, 1}*→Zq 
9. Output of the public parameters params=<q, G1, G2, e, P, Ppub, H1, H2>
10. Output of the master key s
(2) Extract:
Input: the public parameters params, the master key s, any character string ID used as a public key
Output: a private key dID corresponding to ID
Procedure:
1. Calculation of QID=H1(ID)
2. Calculation of dID=sQID 
3. Output of the private key dID 
(3) Sign:
Input: signature object data M, the public parameters params and the private key dID of the signer
Output: a signature (u, v)
Procedure:
1. Random selection of kεZq*
2. Random selection of P1εG1*
3. Calculation of r=e(P1, P)k 
4. Calculation of v=H2(M, r)
5. Calculation of u=vdID+kP1 
6. Output of the signature (u, v)
(4) Verify:
Input: the signature (u, v), the signature object data M, the public parameter params and the public key ID of the signer
Output: accept or reject
Procedure:
1. Calculation of QID=H1(ID)εG1*
2. Calculation of r=e(u, P)×e(QID, −Ppub)
3. Output of accept if v=H2(M, r) is satisfied, or reject if not
Next, will be described ID-based Signcryption disclosed in Non-patent Document 3. Fundamentally, the system for realizing the ID-based Signcryption is similar to the above-described ID-based public key encryption system and the ID-based digital signature system.
The ID-based Signcryption comprises the following six processes. The processes (1) and (2) are performed in a private key generation center, the processes (3) and (4) on the sender's side, and the processes (5) and (6) on the receiver's side.
(1) Setup: Public parameters including groups and pairing used commonly in the system are generated. Further, a master key is generated. The public parameters are opened to the public. To ensure security of the entire system, the master key is kept under strict surveillance so that the master key should not be leaked to the outside including users of the system.(2) Extract: A private key of a user is generated applying the master key to a character string that can be associated with that user (such as an E-mail address of the user). The character string becomes a public key of that user.(3) Sign: Using the public parameters and a private key of a signer, his signature is generated.(4) Encrypt: Using the public parameters and a public key of a sending destination, encryption object data added with the signature are encrypted. Or, the signature is added to encrypted data.(5) Decrypt: Using the public parameters and a private key of the recipient, the encrypted data are decrypted and the signature is extracted. Or, after extraction of the signature, the encrypted data are decrypted.(6) Verify: Using the public parameters and the public key of the sender, the signature is verified.
Next, will be described input, output and processing specifications in each of the above processes (1)-(6).
(1) Setup: Generation of the Public Parameters and the Master Key
Input: security parameter kεZ+
Output: the public parameters params and the master key s
Procedure:
1. Generation of a k bit prime number q
2. Selection of a group G1 of order q
3. Selection of a group G2 of order q
4. Selection of a pairing e: G1×G1→G2 
5. Selection of a generator P of G1 
6. Random selection of sεZq*, to define Ppub=sP
7. Selection of a hash function H0: {0, 1}*→G1*
8. Selection of a hash function H1: {0, 1}*→Zq*
9. Selection of a hash function H2: G2→{0, 1}*
10. Output of the public parameters params=<q, G1, G2, e, P, Ppub, H0, H1, H2>
11. Output of the master key s
(2) Extract:
Input: the public parameters params, the master key s, and any character string ID used as a public key
Output: a private key dID corresponding to ID
Procedure
1. Calculation of QID=H0(ID)εG1*
2. Calculation and output of the secret key dID=sQID 
(3) Sign and (4) Encrypt (Signature Generation and Encryption)
Input: signature object data M, the public parameters params and a private key dID of a signer
Output: a signature (u, v)
Sign Procedure:
1. Calculation of QA=H0(IDA)
2. Random selection of rεZq*
3. Calculation of X=rQA 
4. Calculation of h=H1(M∥X), where M is the data as the object of signature and encryption
5. Calculation of Z=(r+h)dIDA 
6. Sending of the signature (X, Z) together with (M, r, IDA,dIDA) to Encrypt
Encrypt Procedure:
1. Calculation of QB=H0(IDB)εG1*
2. Calculation of w=e(rdIDA, QB)
3. Calculation of Y=H2(w) XOR (Z∥IDA∥M)
4. Output of C=(X, Y) as cipher text added with the signature
(5) Decrypt and (6). Verify (Decryption+Signature Verification)
Input: the cipher text with the signature (X, Y), the public parameters params, and the public key ID of the signer
Output: accept or reject
Decrypt Procedure:
1. Calculation of w=e(X, dIDB)
2. Calculation of Z∥IDA∥M=H2(w) XOR Y
3. Sending of (IDA, M) and (X, Z) to Verify
Verify Procedure:
4. Calculation of QA=H0(IDA)
5. Calculation of h=H1(M∥X)
6. Verification of e(Z, P)=e(Ppub, hQA), and output of accept if e(Z, P)=e(Ppub, hQA) is satisfied, or reject if not